home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 12 - 1996 / 12.03 Mar 96 / SlidingTiles ƒ / SlidingTiles.c < prev    next >
Encoding:
Text File  |  1996-01-15  |  22.2 KB  |  766 lines  |  [TEXT/R*ch]
  1. // Solution to SlidingTiles MacTech Programmer's Challenge
  2. // Written by Jorg Brown & Eric Gundrum
  3. // Thanks also to Brad Kollmyer
  4.  
  5. #include "Solve.h"
  6.  
  7. static MoveProc gMakeMove;
  8. static long *gTiles, gNumCols;
  9.  
  10. static long *gPieceRow, *gPieceCol;
  11.  
  12. static long *gBlankSquare; // initialized by SolveTiles, updated by BlankXXX()
  13.  
  14. #define gBlankRow pieceRow[0]
  15. #define gBlankCol pieceCol[0]
  16.  
  17. static void BlankUp() { // move the BLANK SQUARE up
  18.    long   tile;
  19.    long   *oldBlankSquare;
  20.    long   *newBlankSquare;
  21.    long   *pieceRow = gPieceRow;
  22.    long   *pieceCol = gPieceCol;
  23.  
  24.    oldBlankSquare = gBlankSquare;
  25.    gBlankSquare = newBlankSquare = oldBlankSquare - gNumCols;
  26.    tile = *newBlankSquare;
  27.    pieceRow[tile] = gBlankRow--;
  28.    gMakeMove(gBlankRow, gBlankCol);
  29.    *oldBlankSquare = tile;
  30.    *newBlankSquare = 0;
  31. }
  32.  
  33. static void BlankDown() { // move the BLANK SQUARE down
  34.    long   tile;
  35.    long   *oldBlankSquare;
  36.    long   *newBlankSquare;
  37.    long   *pieceRow = gPieceRow;
  38.    long   *pieceCol = gPieceCol;
  39.  
  40.    oldBlankSquare = gBlankSquare;
  41.    gBlankSquare = newBlankSquare = oldBlankSquare + gNumCols;
  42.    tile = *newBlankSquare;
  43.    pieceRow[tile] = gBlankRow++;
  44.    gMakeMove(gBlankRow, gBlankCol);
  45.    *oldBlankSquare = tile;
  46.    *newBlankSquare = 0;
  47. }
  48.  
  49. static void MoveBlankToRow(long destRow) {
  50.    long   tile;
  51.    long   *oldBlankSquare;
  52.    long   *newBlankSquare;
  53.    long   *pieceRow = gPieceRow;
  54.    long   *pieceCol = gPieceCol;
  55.    long   blankRow = gBlankRow;
  56.  
  57.    long   rowInc;
  58.    long   BlankSquareInc;
  59.  
  60.    if (blankRow < destRow) { // move DOWN
  61.       rowInc = 1;
  62.       BlankSquareInc = gNumCols;
  63.    } else if (blankRow > destRow) { // move UP
  64.       rowInc = -1;
  65.       BlankSquareInc = -gNumCols;
  66.    } else return;
  67.  
  68.    oldBlankSquare = gBlankSquare;
  69.    do {
  70.       newBlankSquare = oldBlankSquare + BlankSquareInc;
  71.       tile = *newBlankSquare;
  72.       pieceRow[tile] = blankRow;
  73.       blankRow += rowInc;
  74.       gMakeMove(blankRow, gBlankCol);
  75.       *oldBlankSquare = tile;
  76.       *newBlankSquare = 0;
  77.       oldBlankSquare = newBlankSquare;
  78.    } while (blankRow != destRow);
  79.    gBlankSquare = newBlankSquare;
  80.    gBlankRow = blankRow;
  81. }
  82.  
  83. static void BlankLeft() { // move the BLANK SQUARE left
  84.    long   tile;
  85.    long   *oldBlankSquare;
  86.    long   *newBlankSquare;
  87.    long   *pieceRow = gPieceRow;
  88.    long   *pieceCol = gPieceCol;
  89.  
  90.    oldBlankSquare = gBlankSquare;
  91.    gBlankSquare = newBlankSquare = oldBlankSquare - 1;
  92.    tile = *newBlankSquare;
  93.    pieceCol[tile] = gBlankCol--;
  94.    gMakeMove(gBlankRow, gBlankCol);
  95.    *oldBlankSquare = tile;
  96.    *newBlankSquare = 0;
  97. }
  98.  
  99. static void BlankRight() { // move the BLANK SQUARE right
  100.    long   tile;
  101.    long   *oldBlankSquare;
  102.    long   *newBlankSquare;
  103.    long   *pieceRow = gPieceRow;
  104.    long   *pieceCol = gPieceCol;
  105.  
  106.    oldBlankSquare = gBlankSquare;
  107.    gBlankSquare = newBlankSquare = oldBlankSquare + 1;
  108.    tile = *newBlankSquare;
  109.    pieceCol[tile] = gBlankCol++;
  110.    gMakeMove(gBlankRow, gBlankCol);
  111.    *oldBlankSquare = tile;
  112.    *newBlankSquare = 0;
  113. }
  114.  
  115. static void MoveBlankToCol(long destCol) {
  116.    long   tile;
  117.    long   *oldBlankSquare;
  118.    long   *newBlankSquare;
  119.    long   *pieceRow = gPieceRow;
  120.    long   *pieceCol = gPieceCol;
  121.    long   blankCol = gBlankCol;
  122.  
  123.    long   inc;
  124.  
  125.    if (blankCol < destCol) { // move RIGHT
  126.       inc = 1;
  127.    } else if (blankCol > destCol) { // move LEFT
  128.       inc = -1;
  129.    } else return;
  130.  
  131.    oldBlankSquare = gBlankSquare;
  132.    do {
  133.       newBlankSquare = oldBlankSquare + inc;
  134.       tile = *newBlankSquare;
  135.       pieceCol[tile] = blankCol;
  136.       blankCol += inc;
  137.       gMakeMove(gBlankRow, blankCol);
  138.       *oldBlankSquare = tile;
  139.       *newBlankSquare = 0;
  140.       oldBlankSquare = newBlankSquare;
  141.    } while (blankCol != destCol);
  142.    gBlankSquare = newBlankSquare;
  143.    gBlankCol = blankCol;
  144. }
  145.  
  146. static void MoveAPiece(long piece, long destRow, long destCol, long 
  147. nextPiece) {
  148.    long   sourceRow;
  149.    long   sourceCol;
  150.    long   *pieceRow = gPieceRow;
  151.    long   *pieceCol = gPieceCol;
  152.    long   nextRow = gNumCols;
  153.  
  154.    sourceRow = pieceRow[piece];
  155.    sourceCol = pieceCol[piece];
  156.  
  157.    if (sourceRow >= destRow) { // in this case, we have to move the tile up (or directly right) to get to its destination
  158.       if (sourceRow == destRow) {
  159.          if (sourceCol == destCol) return;
  160.  
  161.          // simplify: move the blank so that it is not to the right of the target
  162.          if (gBlankCol > destCol) {
  163.             MoveBlankToCol(destCol);
  164.          }
  165.  
  166.          // move the blank to the left of the source, possibly moving the source
  167.          // to the right at the same time.
  168.          if (gBlankRow != destRow) {
  169.             if (sourceCol == destCol - 1 && gBlankRow > destRow) {
  170.                MoveBlankToCol(sourceCol - 1);
  171.                MoveBlankToRow(sourceRow - 1);
  172.                BlankRight();
  173.                BlankRight();
  174.                BlankDown();
  175.                BlankLeft();
  176.                return; // all done
  177.             } else {
  178.                MoveBlankToCol(sourceCol + 1);
  179.                MoveBlankToRow(sourceRow);
  180.                BlankLeft();
  181.                sourceCol++;
  182.             }
  183.          } else {
  184.             if (gBlankCol < sourceCol) {
  185.                MoveBlankToCol(sourceCol - 1);
  186.             } else {
  187.                MoveBlankToCol(sourceCol);
  188.                sourceCol++;
  189.             }
  190.          }
  191.          
  192. WereOnTheSameRowNow:
  193.          // at this point, the blank is to the left of the source,
  194.          // and the puzzle might very well be done already.
  195.          while (sourceCol != destCol) {
  196.             if (nextPiece == piece - 1) { // into a row?
  197.                if (gBlankCol != 0 && pieceCol[nextPiece]-pieceRow[nextPiece] <= gBlankCol-gBlankRow) {
  198.                   MoveAPiece(nextPiece, gBlankRow, gBlankCol, nextPiece - 1);
  199.                }
  200.                if (gBlankRow == destRow) while ((gBlankSquare[-1] == gBlankSquare[1] - 1) && gBlankCol != 0) {
  201.                   BlankLeft();
  202.                }
  203.             }
  204.             if (gBlankRow == destRow) BlankUp();
  205.             do {
  206.                BlankRight();
  207.             } while (gBlankCol <= sourceCol);
  208.             BlankDown();
  209.             BlankLeft();
  210.             sourceCol++;
  211.          }
  212.          return;
  213.       }
  214.       // simplify: move the blank so that it is to the left of the target
  215.       if (gBlankCol >= destCol) {
  216.          MoveBlankToCol(destCol - 1);
  217.       }
  218.       // simplify: move the blank so that it is not above the target.
  219.       if (gBlankRow < destRow) MoveBlankToRow(destRow);
  220.  
  221. again1:   // simplify: if the blank is below the source, move it so it's not.
  222.       sourceRow = pieceRow[piece];
  223.       sourceCol = pieceCol[piece];
  224.       if (gBlankRow >= sourceRow) {
  225.          // if the blank is in the same column, move it away first.
  226.          if (gBlankCol == sourceCol) {
  227.             if (gBlankCol == destCol - 1) {
  228.                BlankLeft();
  229.             } else {
  230.                BlankRight();
  231.             }
  232.          }
  233.          // now that they're in different columns, move the blank so it's not below
  234.          MoveBlankToRow(sourceRow);
  235.       }
  236.       // simplify: if the blank is on the same row, and to the left, move up.
  237.       if (gBlankRow == sourceRow && gBlankCol < sourceCol) {
  238.          BlankUp();
  239.       }
  240.       // simplify: if the blank is to the left, move it to the same column.
  241.       if (gBlankCol < sourceCol) {
  242.          MoveBlankToCol(sourceCol);
  243.       }
  244.       // simplify: if the blank is to the upper right, move it to the left and down.
  245.       if (gBlankRow < sourceRow) {
  246.          if (gBlankCol > sourceCol) {
  247.             MoveBlankToCol(sourceCol);
  248.          }
  249.          if (gBlankRow < sourceRow - 1) {
  250.             MoveBlankToRow(sourceRow - 1);
  251.          }
  252.       }
  253.       // if the blank is off to the right, move it next to the source.
  254.       while (gBlankCol > sourceCol + 1) {
  255.          MoveBlankToCol(sourceCol + 1);
  256.       }
  257.       // at this point, the blank should be either just above or just right of the piece.
  258.       if (gBlankCol == sourceCol) {
  259.          if (gBlankRow != sourceRow - 1) Debugger();
  260.       } else {
  261.          if (gBlankRow != sourceRow) Debugger();
  262.          if (gBlankCol != sourceCol + 1) Debugger();
  263.          BlankLeft();
  264.          BlankUp();
  265.          BlankRight();
  266.       }
  267.       BlankDown();
  268.       sourceRow = pieceRow[piece];
  269.       sourceCol = pieceCol[piece];
  270.       if (sourceRow != destRow) goto again1;
  271.       if (gBlankCol != destCol - 1) {
  272.          BlankRight();
  273.          BlankUp();
  274.          BlankLeft();
  275.          while (pieceCol[piece] != destCol) {
  276.             BlankUp();
  277.             BlankRight();
  278.             BlankRight();
  279.             BlankDown();
  280.             BlankLeft();
  281.          }
  282.          return; // DONE!!!!
  283.       }
  284.       BlankLeft();
  285.       BlankUp();
  286.       BlankUp();
  287.       BlankRight();
  288.       BlankRight();
  289.       BlankDown();
  290.       BlankLeft();
  291.       return; // DONE!!!!
  292.    }
  293.  
  294.    // at this point, we know that source is above our destination.
  295.    if (sourceCol >= destCol) { // in this case, we have to move the tile left (or directly down) to get to its destination
  296.       if (sourceCol == destCol) {
  297.  
  298.          // simplify: move the blank so that it is not below the target
  299.          if (gBlankRow > destRow) {
  300.             MoveBlankToRow(destRow);
  301.          }
  302.  
  303.          // move the blank above the source, possibly moving the source
  304.          // down at the same time.
  305.          if (gBlankCol != destCol) {
  306.             if (sourceRow == destRow - 1 && gBlankCol > destCol) {
  307.                MoveBlankToRow(sourceRow - 1);
  308.                MoveBlankToCol(sourceCol - 1);
  309.                BlankDown();
  310.                BlankDown();
  311.                BlankRight();
  312.                BlankUp();
  313.                return; // all done
  314.             } else {
  315.                MoveBlankToRow(sourceRow + 1);
  316.                MoveBlankToCol(sourceCol);
  317.                BlankUp();
  318.                sourceRow++;
  319.             }
  320.          } else {
  321.             if (gBlankRow < sourceRow) {
  322.                MoveBlankToRow(sourceRow - 1);
  323.             } else {
  324.                MoveBlankToRow(sourceRow);
  325.                sourceRow++;
  326.             }
  327.          }
  328.          
  329. WereInTheSameColumnNow:
  330.          // at this point, the blank is on top of the source,
  331.          // and the puzzle might very well be done already.
  332.          while (sourceRow != destRow) {
  333.             if (nextPiece == piece - nextRow) { // into a column?
  334.                if (gBlankRow != 0 && pieceCol[nextPiece]-pieceRow[nextPiece] >= gBlankCol-gBlankRow) {
  335.                   MoveAPiece(nextPiece, gBlankRow, gBlankCol, nextPiece - nextRow);
  336.                }
  337.                if (gBlankCol == destCol) while ((gBlankSquare[-nextRow] == gBlankSquare[nextRow] - 1) && gBlankRow != 0) {
  338.                   BlankUp();
  339.                }
  340.             }
  341.             if (gBlankCol == destCol) BlankLeft();
  342.             do {
  343.                BlankDown();
  344.             } while (gBlankRow <= sourceRow);
  345.             BlankRight();
  346.             BlankUp();
  347.             sourceRow++;
  348.          }
  349.          return;
  350.       }
  351.       // simplify: move the blank so that it is to the up of the target
  352.       if (gBlankRow >= destRow) {
  353.          MoveBlankToRow(destRow - 1);
  354.       }
  355.       // simplify: move the blank so that it is not to the left of the target.
  356.       if (gBlankCol < destCol) MoveBlankToCol(destCol);
  357.  
  358. again2:   // simplify: if the blank is to the right of the source, move it so it's not.
  359.       sourceRow = pieceRow[piece];
  360.       sourceCol = pieceCol[piece];
  361.       if (gBlankCol >= sourceCol) {
  362.          // if the blank is in the same row, move it away first.
  363.          if (gBlankRow == sourceRow) {
  364.             if (gBlankRow == destRow - 1) {
  365.                BlankUp();
  366.             } else {
  367.                BlankDown();
  368.             }
  369.          }
  370.          // now that they're in different rows, move the blank so it's not to the right of
  371.          MoveBlankToCol(sourceCol);
  372.       }
  373.       // simplify: if the blank is on the same column, and to the up, move left.
  374.       if (gBlankCol == sourceCol && gBlankRow < sourceRow) {
  375.          BlankLeft();
  376.       }
  377.       // simplify: if the blank is to the up, move it to the same row.
  378.       if (gBlankRow < sourceRow) {
  379.          MoveBlankToRow(sourceRow);
  380.       }
  381.       // simplify: if the blank is to the lower left, move it to the right and up.
  382.       if (gBlankCol < sourceCol) {
  383.          if (gBlankRow > sourceRow) {
  384.             MoveBlankToRow(sourceRow);
  385.          }
  386.          if (gBlankCol < sourceCol - 1) {
  387.             MoveBlankToCol(sourceCol - 1);
  388.          }
  389.       }
  390.       // if the blank is off to the down, move it next to the source.
  391.       while (gBlankRow > sourceRow + 1) {
  392.          MoveBlankToRow(sourceRow + 1);
  393.       }
  394.       // at this point, the blank should be either just below or just to the left of the piece.
  395.       if (gBlankRow == sourceRow) {
  396.          if (gBlankCol != sourceCol - 1) Debugger();
  397.       } else {
  398.          if (gBlankCol != sourceCol) Debugger();
  399.          if (gBlankRow != sourceRow + 1) Debugger();
  400.          BlankUp();
  401.          BlankLeft();
  402.          BlankDown();
  403.       }
  404.       BlankRight();
  405.       sourceRow = pieceRow[piece];
  406.       sourceCol = pieceCol[piece];
  407.       if (sourceCol != destCol) goto again2;
  408.       if (gBlankRow != destRow - 1) {
  409.          BlankDown();
  410.          BlankLeft();
  411.          BlankUp();
  412.          while (pieceRow[piece] != destRow) {
  413.             BlankLeft();
  414.             BlankDown();
  415.             BlankDown();
  416.             BlankRight();
  417.             BlankUp();
  418.          }
  419.          return; // DONE!!!!
  420.       }
  421.       BlankUp();
  422.       BlankLeft();
  423.       
  424.       BlankLeft();
  425.       BlankDown();
  426.       BlankDown();
  427.       BlankRight();
  428.       BlankUp();
  429.       return; // DONE!!!!
  430.    }
  431.  
  432.    // at this point, we know that we are above and to the left of our destination.
  433.  
  434.    if (destCol - sourceCol == destRow - sourceRow) {
  435.       // we're on the diagonal.
  436.       if (gBlankCol >= sourceCol) {
  437.          if (gBlankRow <= sourceRow) goto MoveSrcRightFirst;
  438.       }
  439.       if (gBlankRow >= sourceRow) {
  440.          if (gBlankCol <= sourceCol) goto MoveSrcDownFirst;
  441.       }
  442.       if (gPieceRow[nextPiece] - gPieceCol[nextPiece] > destRow - destCol) {
  443.          // relative to the destination, the next piece is to the lower left.
  444.          // this means we want the blank to end up to the left of the target,
  445.          // rather than above it.
  446.          goto MoveSrcDownFirst;
  447.       }
  448.       goto MoveSrcRightFirst;
  449.    }
  450.    if (destCol - sourceCol < destRow - sourceRow) {
  451. MoveSrcDownFirst:
  452.       // the source is within the 90-135' octant.
  453.       // we want to move the blank square just below the source.
  454.       // we will end up just to the left of the target.
  455.       if (gBlankCol == sourceCol && gBlankRow < sourceRow) {
  456.          // the blank is on top of the source.  moving it
  457.          // down would move our square in the wrong direction.
  458.          BlankRight();
  459.       }
  460.       // in case the source is just to the upper left of the target,
  461.       // we have to make sure we don't accidentally munge the
  462.       // protected area.
  463.       if (gBlankCol > destCol) MoveBlankToCol(destCol);
  464.       MoveBlankToRow(sourceRow + 1);
  465.       MoveBlankToCol(sourceCol);
  466.       BlankUp();
  467.       sourceRow++;
  468.       BlankRight();
  469.       BlankDown();
  470.       // the blank is now to the right of the source.
  471.    } else {
  472. MoveSrcRightFirst:
  473.       // the source is within the 135-180' octant.
  474.       // we want to move the blank square just to the right of the source.
  475.       // we will end up just above the target.
  476.       if (gBlankRow == sourceRow && gBlankCol < sourceCol) {
  477.          // the blank is to the left of the source.  moving it
  478.          // to the right would move our square in the wrong direction.
  479.          BlankDown();
  480.       }
  481.       // in case the source is just to the upper left of the target,
  482.       // we have to make sure we don't accidentally munge the
  483.       // protected area.
  484.       if (gBlankRow > destRow) MoveBlankToRow(destRow);
  485.       MoveBlankToCol(sourceCol + 1);
  486.       MoveBlankToRow(sourceRow);
  487.       // the blank is now to the right of the source.
  488.    }
  489.    BlankLeft();
  490.    sourceCol++;
  491.    // the blank is now to the left of the source.
  492.    // are we done yet?
  493.    for (;;) {
  494.       if (sourceCol == destCol) {
  495.          if (sourceRow == destRow) return;
  496.          // the blank is still to the left of the source.
  497.          BlankDown();
  498.          BlankRight();
  499.          BlankUp();
  500.          sourceRow++;
  501.          goto WereInTheSameColumnNow;
  502.       }
  503.       if (sourceRow == destRow) {
  504.          goto WereOnTheSameRowNow;
  505.       }
  506.       BlankDown();
  507.       BlankRight();
  508.       BlankUp();
  509.       sourceRow++;
  510.       BlankRight();
  511.       BlankDown();
  512.       BlankLeft();
  513.       sourceCol++;
  514.    }
  515. }
  516.  
  517. static void *QuickBlock(long size) {
  518.    Handle   h = NewHandle(size);
  519.  
  520.    if (h == 0) return 0;
  521.    HLock(h);
  522.    return *h;
  523. }
  524.  
  525. static void DisposeBlock(void *block) {
  526.    Handle   h = RecoverHandle(block);
  527.  
  528.    DisposeHandle(h);
  529. }
  530.  
  531. void SolveTiles(
  532.   long *tiles,      /* pointer to array of tiles where         */
  533.   long numRows,     /*   tile (row,col) is at                  */
  534.   long numCols,     /*   *(tiles + row*numCols + col)          */
  535.   MoveProc MakeMove /* Callback procedure to move a tile       */
  536. ) {
  537.    long   col, row, target, tile, correctTile;
  538.    long   colsToGo, rowsToGo;
  539.    long   *tileRover;
  540.    long   *pieceRow, *pieceCol;
  541.  
  542.    pieceRow = QuickBlock(numRows * numCols * sizeof(long));
  543.    if (pieceRow == 0) return;
  544.  
  545.    pieceCol = QuickBlock(numRows * numCols * sizeof(long));
  546.    if (pieceCol == 0) {
  547.       DisposeBlock(pieceRow);
  548.       return;
  549.    }
  550.    gPieceRow = pieceRow;
  551.    gPieceCol = pieceCol;
  552.  
  553.    gMakeMove = MakeMove;
  554.    gTiles = tiles;
  555.    gNumCols = numCols;
  556.  
  557.    tileRover = tiles;
  558.    correctTile = 0;
  559.    for (row = 0; row < numRows; row++) {
  560.       for (col = 0; col < numCols; col++) {
  561.          tile = *tileRover++;
  562.          pieceRow[tile] = row;
  563.          pieceCol[tile] = col;
  564.          correctTile++;
  565.       }
  566.    }
  567.  
  568.    gBlankSquare = &tiles[gBlankRow * numCols + gBlankCol];
  569.  
  570.    rowsToGo = numRows;
  571.    colsToGo = numCols;
  572.  
  573.    for (;;) {
  574.       if (rowsToGo >= colsToGo) {
  575.          if (rowsToGo <= 2) break;
  576.          row = rowsToGo - 1;
  577.          for (col = colsToGo - 1; col > 1; col--) {
  578.             tile = row * numCols + col;
  579.             MoveAPiece(tile, row, col, tile - 1);
  580.          }
  581.          tile = row * numCols;
  582.          if (pieceRow[tile]     != row || pieceCol[tile    ] != 0 ||
  583.              pieceRow[tile + 1] != row || pieceCol[tile + 1] != 1) {
  584.             MoveAPiece(tile, row, 1, tile + 1);
  585.             if (gBlankRow == row) {
  586.                if (tiles[(row - 1) * numCols] == tile + 1) {
  587.                   // problem scenario 1
  588. rowScenario1:
  589.                   BlankRight();
  590.                   BlankUp();
  591.                   BlankLeft();
  592.                   BlankUp();
  593.                   BlankRight();
  594.                   BlankDown();
  595.                   BlankDown();
  596.                   BlankLeft();
  597.                   BlankUp();
  598.                   BlankRight();
  599.                   BlankUp();
  600.                   BlankLeft();
  601.                   BlankDown();
  602.                   BlankDown();
  603.                   BlankRight();
  604.                   BlankUp();
  605.                   goto nextRow;
  606.                }
  607.             } else if (tiles[row * numCols] == tile + 1) {
  608.                // problem scenario 2
  609.                MoveBlankToCol(0);
  610.                MoveBlankToRow(row);
  611.                goto rowScenario1;
  612.             }
  613.             MoveAPiece(tile + 1, row, 1, 0);
  614.          }
  615. nextRow:   if (gBlankRow == row) BlankUp();
  616.          if (pieceRow[tile]     != row || pieceCol[tile    ] != 0) {
  617.             // the "12" isn't in place...
  618.             Debugger();
  619.             Debugger();
  620.             Debugger();
  621.             Debugger();
  622.          }
  623.       rowsToGo--;
  624.       } else {
  625.          if (colsToGo <= 2) break;
  626.          col = colsToGo - 1;
  627.          for (row = rowsToGo - 1; row > 1; row--) {
  628.             tile = row * numCols + col;
  629.             MoveAPiece(tile, row, col, tile - numCols);
  630.          }
  631.          if (pieceRow[          col] != 0 || pieceCol[          col] != col ||
  632.              pieceRow[numCols + col] != 1 || pieceCol[numCols + col] != col) {
  633.             MoveAPiece(col, 1, col, col + numCols);
  634.             if (gBlankCol == col) {
  635.                if (tiles[col - 1] == numCols + col) {
  636.                   // problem scenario 1
  637. colScenario1:
  638.                   BlankDown();
  639.                   BlankLeft();
  640.                   BlankUp();
  641.                   BlankLeft();
  642.                   BlankDown();
  643.                   BlankRight();
  644.                   BlankRight();
  645.                   BlankUp();
  646.                   BlankLeft();
  647.                   BlankDown();
  648.                   BlankLeft();
  649.                   BlankUp();
  650.                   BlankRight();
  651.                   BlankRight();
  652.                   BlankDown();
  653.                   BlankLeft();
  654.                   goto nextCol;
  655.                }
  656.             } else if (tiles[col] == numCols + col) {
  657.                // problem scenario 2
  658.                MoveBlankToRow(0);
  659.                MoveBlankToCol(col);
  660.                goto colScenario1;
  661.             }
  662.             MoveAPiece(numCols + col, 1, col, 0);
  663.          }
  664. nextCol:   if (gBlankCol == col) BlankLeft();
  665.          if (pieceRow[          col] != 0 || pieceCol[          col] != col) {
  666.             // the "3" isn't in place...
  667.             Debugger();
  668.             Debugger();
  669.             Debugger();
  670.             Debugger();
  671.          }
  672.          colsToGo--;
  673.       }
  674.    }
  675.  
  676.    if (gBlankRow == 0) {
  677.       if (gBlankCol == 0) {
  678.          if (pieceRow[1] == 0) goto pos0123;
  679.          if (pieceCol[1] == 0) goto pos0312;
  680.                                 goto pos0231;
  681.       } else {
  682.          if (pieceRow[1] == 0) goto pos1023;
  683.          if (pieceCol[1] == 0) goto pos3012;
  684.                                 goto pos2031;
  685.       }
  686.    } else {
  687.       if (gBlankCol == 0) {
  688.          if (pieceRow[1] != 0) goto pos3201;
  689.          if (pieceCol[1] == 0) goto pos1302;
  690.                                 goto pos2103;
  691.       } else {
  692.          if (pieceRow[1] != 0) goto pos3210;
  693.          if (pieceCol[1] == 0) goto pos1320;
  694.                                 goto pos2130;
  695.       }
  696.    }
  697.  
  698.    // 30
  699.    // 12
  700. pos3012:
  701.    BlankLeft();
  702.  
  703.    // 03
  704.    // 12
  705. pos0312:
  706.    BlankDown();
  707.  
  708.    // 13
  709.    // 02
  710. pos1302:
  711.    BlankRight();
  712.  
  713.    // 13
  714.    // 20
  715. pos1320:
  716.    BlankUp();
  717.  
  718.    // 10
  719.    // 23
  720. pos1023:
  721.    BlankLeft();
  722.  
  723.    // 01
  724.    // 23
  725.    goto all_done;
  726.  
  727.    // 32
  728.    // 10
  729. pos3210:
  730.    BlankLeft();
  731.  
  732.    // 32
  733.    // 01
  734. pos3201:
  735.    BlankUp();
  736.  
  737.    // 02
  738.    // 31
  739. pos0231:
  740.    BlankRight();
  741.  
  742.    // 20
  743.    // 31
  744. pos2031:
  745.    BlankDown();
  746.  
  747.    // 21
  748.    // 30
  749. pos2130:
  750.    BlankLeft();
  751.  
  752.    // 21
  753.    // 03
  754. pos2103:
  755.    BlankUp();
  756.  
  757.    // 01
  758.    // 23
  759. pos0123:
  760.    goto all_done;
  761.  
  762. all_done:
  763.    DisposeBlock(pieceRow); gPieceRow = 0;
  764.    DisposeBlock(pieceCol); gPieceCol = 0;
  765. }
  766.